<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    547. Friend Circles
   </h1>
   <p>
    There are
    <b>
     N
    </b>
    students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a
    <b>
     direct
    </b>
    friend of B, and B is a
    <b>
     direct
    </b>
    friend of C, then A is an
    <b>
     indirect
    </b>
    friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
   </p>
   <p>
    Given a
    <b>
     N*N
    </b>
    matrix
    <b>
     M
    </b>
    representing the friend relationship between students in the class. If M[i][j] = 1, then the i
    <sub>
     th
    </sub>
    and j
    <sub>
     th
    </sub>
    students are
    <b>
     direct
    </b>
    friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
   </p>
   <p>
    <b>
     Example 1:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
<b>Output:</b> 2
<b>Explanation:</b>The 0<sub>th</sub> and 1<sub>st</sub> students are direct friends, so they are in a friend circle. <br>The 2<sub>nd</sub> student himself is in a friend circle. So return 2.
</pre>
   <p>
    <b>
     Example 2:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
<b>Output:</b> 1
<b>Explanation:</b>The 0<sub>th</sub> and 1<sub>st</sub> students are direct friends, the 1<sub>st</sub> and 2<sub>nd</sub> students are direct friends, <br>so the 0<sub>th</sub> and 2<sub>nd</sub> students are indirect friends. All of them are in the same friend circle, so return 1.
</pre>
   <p>
    <b>
     Note:
    </b>
    <br>
   </p>
   <ol>
    <li>
     N is in range [1,200].
    </li>
    <li>
     M[i][i] = 1 for all students.
    </li>
    <li>
     If M[i][j] = 1, then M[j][i] = 1.
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    547. 朋友圈
   </h1>
   <p>
    班上有&nbsp;
    <strong>
     N&nbsp;
    </strong>
    名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B&nbsp;的朋友，B 是 C&nbsp;的朋友，那么我们可以认为 A 也是 C&nbsp;的朋友。所谓的朋友圈，是指所有朋友的集合。
   </p>
   <p>
    给定一个&nbsp;
    <strong>
     N * N&nbsp;
    </strong>
    的矩阵&nbsp;
    <strong>
     M
    </strong>
    ，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生
    <strong>
     互为
    </strong>
    朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
   </p>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
<strong>输出:</strong> 2 
<strong>说明：</strong>已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
<strong>输出:</strong> 1
<strong>说明：</strong>已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
</pre>
   <p>
    <strong>
     注意：
    </strong>
   </p>
   <ol>
    <li>
     N 在[1,200]的范围内。
    </li>
    <li>
     对于所有学生，有M[i][i] = 1。
    </li>
    <li>
     如果有M[i][j] = 1，则有M[j][i] = 1。
    </li>
   </ol>
  </div>
 </body>
</html>